package com.feiyue.learning.sort;

import java.util.Arrays;

/**
 * 归并排序
 * @author  feiyue
 * @date  2020/3/30
 */
public class MergeSort {

    // 辅助数组
    static int[] aux;

    public static void main(String[] args) {
        int[] data = new int[]{2, 3, 5, 4, 7, 6, 8, 1};

        System.out.print("排序前: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));

        sort(data);

        System.out.print("\n排序后: ");
        Arrays.stream(data).forEach(r->System.out.print(r + " "));
    }

    private static void sort(int[] data) {
        aux = new int[data.length];
        mergeSort(data, 0, data.length - 1);
    }

    private static void mergeSort(int[] data, int low, int high) {
        if (low >= high) return;
        int middle = (low + high) / 2;
        mergeSort(data, low, middle);
        mergeSort(data, middle + 1, high);
        merge(data, low, high);
    }

    private static void merge(int[] data, int low, int high) {
        int middle = (low + high) / 2;
        int left = low;
        int right = middle + 1;

        for (int i = low; i <= high; i++) {
            aux[i] = data[i];
        }

        for (int k = low; k <= high; k++) {

            // 先处理极限情况
            if (left > middle) {
                data[k] = aux[right++];
                continue;
            }

            if (right > high) {
                data[k] = aux[left++];
                continue;
            }

            if (data[left] < data[right]) {
                data[k] = aux[left++];
            } else {
                data[k] = aux[right++];
            }
        }
    }
}
